// N皇后问题 (位运算实现)
// 测试链接 : https://leetcode.cn/problems/n-queens-ii/
public class NQueens2 {
    public int totalNQueens(int n) {
        if(n < 1){
            return 0;
        }
        //生成一个最右侧二进制n个全是1的数
        int limit = (1<<n) - 1;
        return func(limit, 0, 0, 0) ;
    }

    public int func(int limit, int col, int left, int right){
        if(col == limit){
            return 1;
        }

        //1表示不能成为皇后，0表示可以成为皇后
        int ban = col | left | right;
        //候选项，1表示可以成为皇后，0不能成为皇后
        int candidate = limit & (~ban);
        int place;
        int ans = 0;
        while (candidate != 0 ){
            //获取最右边的那个1
            place = candidate & (-candidate);
            candidate = place ^ candidate; //消除最右边的那个1
            ans += func(limit, col | place, (left | place) >> 1, (right | place) <<1);
        }
        return ans;
    }

}
